package com.demo.jzoffer2;

import org.junit.Test;

import java.util.Arrays;

/**
 * @author gy
 * @date 2023/03
 */
public class Test0315_01 {

    /**
     * 一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。
     * 要求时间复杂度是O(n)，空间复杂度是O(1)。
     *
     * 输入：nums = [4,1,4,6]
     * 输出：[1,6] 或 [6,1]
     *
     * 输入：nums = [1,2,10,4,1,4,3,3]
     * 输出：[2,10] 或 [10,2]
     *
     * 2 <= nums.length <= 10000
     * @param nums
     * @return
     */
    public int[] singleNumbers(int[] nums) {
        // 二进制异或的概念：二进制中：相同为0 不同为1
        // 推论：相同的数字 异或为0，同时 任意数字与0异或结果为其本身
        //所以遍历异或整个数组最后得到的结果就是两个只出现一次的数字异或的结果：即 z = x ^ y
        int z = 0; // 任意数字与0异或结果为其本身 故初始化值为0
        for(int i : nums) {
            z ^= i;
        }
        // 二进制与的概念：二进制中 1&0=0 1&1=1 0&1=0 都为1才为 1
        //我们根据异或的性质可以知道：关键：z中至少有一位是1，否则x与y就是相等的。

        //我们通过一个辅助变量m来保存z中哪一位为1.（可能有多个位都为1，我们找到最低位的1即可）。

        //举个例子：z = 10 ^ 2 = 1010 ^ 0010 = 1000,第四位为1.
        //我们将m初始化为1，如果（z & m）的结果等于0说明z的最低为是0
        //我们每次将m左移一位然后跟z做与操作，直到结果不为0.
        //此时m应该等于1000，同z一样，第四位为1.
        int m = 1;
        while((z & m) == 0) {
            // m每次遍历的值： 0001 0010 0100 1000
            m <<= 1;
        }

        //我们遍历数组，将每个数跟m进行与操作，结果为0的作为一组，结果不为0的作为一组
        //例如对于数组：[1,2,10,4,1,4,3,3]，我们把每个数字跟1000做与操作，可以分为下面两组：
        //nums1存放结果为0的: [1, 2, 4, 1, 4, 3, 3]
        //nums2存放结果不为0的: [10] (碰巧nums2中只有一个10，如果原数组中的数字再大一些就不会这样了)

        //此时我们发现问题已经退化为数组中有一个数字只出现了一次
        //分别对nums1和nums2遍历异或就能得到我们预期的x和y
        int x = 0, y = 0; // 任意数字与0异或结果为其本身 故初始化值为0
        for(int i : nums) {
            //这里我们是通过if...else将nums分为了两组，一边遍历一遍异或。
            //跟我们创建俩数组nums1和nums2原理是一样的。
            if((i & m) == 0) {
                x ^= i;
            } else {
                y ^= i;
            }
        }
        return new int[]{x, y};
    }


    @Test
    public void m1() {
        int[] nums = new int[]{1,2,10,4,1,4,3,3};
        System.out.println("===="+ Arrays.toString(this.singleNumbers(nums)));
    }

    @Test
    public void m2() {

    }

}
